package com.fzn3.day05;

import java.util.Arrays;


/**
 * @author fzn
 * 描述：斐波那契数列
 * f0   f1 f2  f3  f4 f5  f6   f7  f8
 * 0   1   1   2   3   5   8   13  21
 * @program DataStructure
 * @create 2023/3/10 9:06
 **/
public class Fibonacci {
    // 优化版 空间换时间
    public static int fibonacci(int n) {
        int[] cache = new int[n + 1];
        Arrays.fill(cache, -1);
        cache[0] = 0;
        cache[1] = 1;
        return f2(n, cache);
    }

    public static int f2(int n, int[] cache) {
        if (cache[n] != -1) {
            return cache[n];
        }
        int x = f2(n - 1, cache);
        int y = f2(n - 2, cache);
        // 存入数组
        cache[n] = x + y;
        return cache[n];
    }


    public static int f(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        int x = f(n - 1);
        int y = f(n - 2);
        return x + y;
    }

    public static void main(String[] args) {
        int f = fibonacci(8);
        System.out.println(f);
    }
}
